package demo;

import java.util.Deque;
import java.util.LinkedList;

class MyStack {
    Deque<Integer> deque1 ;
    Deque<Integer> deque2 ;

    public MyStack() {
        deque1 = new LinkedList<>();
        deque2 = new LinkedList<>();
    }

    public void push(int x) {
        if(empty() || deque1.size() != 0){
            deque1.offerFirst(x);
        }else{
            deque2.offerFirst(x);
        }
    }

    public int pop() {
        if(deque1.size()!=0){
            //往deque2移动size()-1个
            int size = deque1.size();
            for(int i = 0;i< size-1;i++){
                deque2.offerFirst(deque1.pollLast());
            }
            return deque1.pollLast();
        }else{
            //往deque1移动size()-1个
            int size = deque2.size();
            for(int i = 0;i<size -1;i++){
                deque1.offerFirst(deque2.pollLast());
            }
            return deque2.pollLast();
        }
    }

    public int top() {
        int ret = 0;
        if(deque1.size()!=0){
            //往deque2移动size()个
            int size = deque1.size();
            for(int i = 0;i<size;i++){
                ret = deque1.pollLast();
                deque2.offerFirst(ret);
            }
            return ret;
        }else{
            //往deque1移动size()个
            int size = deque2.size();
            for(int i = 0;i<size;i++){
                ret = deque2.pollLast();
                deque1.offerFirst(ret);
            }
            return ret;
        }
    }

    public boolean empty() {
        return deque1.size() == 0 && deque2.size() == 0;
    }

    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        System.out.println(s.top());
        System.out.println(s.pop());

    }
}